package week_four;

import java.util.*;

public class MinimumGeneticMutation_433 {

    private Set<String> set;
    char[] chars;
    private Map<String, Integer> depth;

    private PriorityQueue<Integer> p = new PriorityQueue<>();

    public int minMutation(String start, String end, String[] bank) {
        set = new HashSet<>();
        depth = new HashMap<>();
        Collections.addAll(set, bank);
        chars = new char[]{'A', 'C', 'G', 'T'};
        return bfs(start, end);
    }

    private int bfs(String start, String end) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        depth.put(start, 0);
        while (!queue.isEmpty()) {
            String s = queue.poll();
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 4; j++) {
                    if (s.charAt(i) == chars[j]) continue;
                    String newStr = s.substring(0, i) + chars[j] + s.substring(i + 1);
                    if (set.contains(newStr) && !depth.containsKey(newStr)) {
                        if (newStr.equals(end)) return depth.get(s) + 1;
                        queue.offer(newStr);
                        depth.put(newStr, depth.get(s) + 1);
                    }
                }
            }
        }
        return -1;
    }
}
